<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
  //封装二叉搜索树
  function BinarySerachTree(){

    //树中的节点
    function Node(key){
      this.key = key
      this.left = null
      this.right = null
    }

  //  属性
    this.root = null //根节点

  //  方法
  //  插入方法：对外给用户调用的方法
    BinarySerachTree.prototype.insert = function(key){
    //  1、根据key创建节点
      var newNode = new Node(key)

    //  2、判断根节点是否有值
      if(this.root == null){
        this.root = newNode //当根节点为空时，newNode就为根节点
      }else{
        this.insertNode(this.root,newNode)
      }

    }

  // 递归方法
    BinarySerachTree.prototype.insertNode = function(node,newNode){
      if(newNode.key < node.key){ //当新节点的key小于当前对比节点的key时，向左查找
        if(node.left == null){ //当前节点左边的子节点为空的话就进行插入
          node.left = newNode
        }else{ //如果不是空继续向下查找，直到找到空的为止
          this.insertNode(node.left,newNode) //递归
        }
      }else{ //当新节点的key大于当前对比节点的key时，向右查找
        if(node.right == null){
          node.right = newNode
        }else{
          this.insertNode(node.right,newNode)
        }
      }
    }

  //  树的遍历
  //    1、先序遍历
      BinarySerachTree.prototype.preOrderTraversal = function(handler){ //header:处理输出的函数
        this.preOrderTraversalNode(this.root,handler)
      }

      BinarySerachTree.prototype.preOrderTraversalNode = function(node,handler){
        if(node != null){
        //    1、处理经过的节点
            handler(node.key)
        //    2、处理经过节点的左子节点
            this.preOrderTraversalNode(node.left,handler)

        //    3、处理经过节点的右子节点
            this.preOrderTraversalNode(node.right,handler)

        }
      }

  //    2、中序遍历
      BinarySerachTree.prototype.midOrderTraversal = function(handler){ //header:处理输出的函数
          this.midOrderTraversalNode(this.root,handler)
      }

      BinarySerachTree.prototype.midOrderTraversalNode = function(node,handler){
          if(node != null){
              //    1、处理左子树中的节点
              this.midOrderTraversalNode(node.left,handler)

              //    2、处理经过的节点
              handler(node.key)

              //    3、处理右子树中的节点
              this.midOrderTraversalNode(node.right,handler)

          }
      }

  //    3、后序遍历
      BinarySerachTree.prototype.postOrderTraversal = function(handler){ //header:处理输出的函数
          this.postOrderTraversalNode(this.root,handler)
      }

      BinarySerachTree.prototype.postOrderTraversalNode = function(node,handler){
          if(node != null){
              //    1、处理左子树中的节点
              this.postOrderTraversalNode(node.left,handler)

              //    2、处理右子树中的节点
              this.postOrderTraversalNode(node.right,handler)

              //    3、处理经过的节点
              handler(node.key)

          }
      }

  //    查找最大&最小值
  //    查找最大值
      BinarySerachTree.prototype.max = function(){
      //  1、获取根节点
          var node = this.root

      //  2、依次向右不断的查找，直到节点为null
          var key = null
          while(node != null){
              key = node.key
              node = node.right
          }

          return key
      }

      //查找最小值
      BinarySerachTree.prototype.min = function(){
          //  1、获取根节点
          var node = this.root

          //  2、依次向右不断的查找，直到节点为null
          var key = null
          while(node != null){
              key = node.key
              node = node.left
          }

          return key
      }

  //    搜索某一个key
      BinarySerachTree.prototype.search = function(key){
      //  1、获取根节点
          var node = this.root

      //  2、循环搜索
          while(node != null){
              if(key < node.key){ //当搜索的key小于当前节点的key，向左子节点找，直到找到为止返回true
                  node = node.left
              }else if(key > node.key){//当搜索的key大于当前节点的key，向右子节点找
                  node = node.right
              }else{
                  return true
              }
          }
          return false //没有找到返回false
      }

  //    删除节点
      BinarySerachTree.prototype.remove = function(key){
      //  1、寻找要删除的节点
      //    1.1、定义变量，保存一些信息
          var current = this.root //指向当前所在节点
          var parent = null //指向当前节点的上一个节点
          var isLeftChild = true //是否经过左子节点

      //    1.2、开始寻找删除的节点
          while(current.key != key){ //没有找到要删除的节点
              parent = current
              if(key < current.key){ //要删除接节点的key小于当前遍历到节点的key
                  isLeftChild = true //继续向左遍历
                  current = current.left
              }else{
                  isLeftChild = false //向右遍历
                  current = current.right
              }

          // 某种情况：已经找到了最后的节点了，依然没有找到==key
              if(current == null){
                  return false
              }
          }

      //  2、根据对应的情况删除节点
      //    2.1、删除的节点是叶子节点（没有子节点）
          if(current.left == null && current.right == null){
              if(current == this.root){ //只有根节点一个节点
                this.root = null
              }else if(isLeftChild){ //该叶子节点在其父节点的左边
                parent.left = null
              }else{
                parent.right = null
              }
          }

      //    2.2、删除的节点有一个子节点
          else if(current.right == null){ //要删除节点有一个左子节点
            if(current == this.root){ //要删除节点是根节点
                this.root = current.left //将删除节点的左子节点变为根节点
            }else if(isLeftChild){ //删除节点是其父节点的左子节点
                parent.left = current.left //将删除节点的左子节点与其父节点的左子节点对应
            }else{ //删除节点是其父节点的右子节点
                parent.right = current.left
            }
          }else if(current.left == null){ //要删除节点有一个右节点
            if(current == this.root){//要删除节点是根节点
              this.root = current.right
            }else if(isLeftChild){
              parent.left = current.right
            }else{
              parent.right = current.right
            }
          }

      //    2.3、删除的节点右两个子节点
          else{
          //    1、获取后续节点
              var successor = this.getSuccessor(current)

          //    2、判断删除节点是否是根节点
              if(current == this.root){ //要删除节点是根节点
                  this.root = successor
              }else if(isLeftChild){ //要删除节点的父节点含有左子节点
                  parent.left = successor
              }else{ //要删除节点的父节点含有右子节点
                  parent.right = successor
              }

          //    3、将删除节点的左子树 = current.left
              successor.left = current.left //后续节点代替要删除节点
          }

      }

      //找后继的方法(后继：比当前节点大同时最接近当前节点)
      BinarySerachTree.prototype.getSuccessor = function(delNode){ //delNode：要删除的节点
      //  1、定义变量，保存找到的后继
          var successor = delNode
          var current = delNode.right
          var successorParent = delNode

      //  2、循环查找
          while(current != null){ //一直到左子树的叶节点
              successorParent = successor //指向successor所指节点的父节点
              successor = current //指向current所指节点的父节点
              current = current.left
          }

      //  3、判断寻找的后续节点是否直接就是delNode的right节点
          if(successor != delNode.right){ //如果后续节点不是delNode的right节点
              //将后续节点的父节点的左子节点和后续节点的左子节点的右子节点相连
              successorParent.left = successor.right
              successor.right = delNode.right
          }

          return successor
      }

  }

//  测试遍历
//  创建BinarySerachTree实例对象
  var bst = new BinarySerachTree()

  //先序遍历测试
  var resultString = ""
  bst.preOrderTraversal(function(key){
      resultString += key + " "
  })
  alert(resultString)

  //中序遍历测试
  var resultString = ""
  bst.midOrderTraversal(function(key){
      resultString += key + " "
  })
  alert(resultString)

  //后序遍历测试
  var resultString = ""
  bst.postOrderTraversal(function(key){
      resultString += key + " "
  })
  alert(resultString)


</script>
</body>
</html>